home *** CD-ROM | disk | FTP | other *** search
.TH BINARY_TREE .SH NAME Binary_Tree<Type>\f1 A parameterized binary tree class .SH SYNOPSIS #include <cool/Binary_Tree.h> .SH DESCRIPTION The \f3Binary_Tree<Type>\f1 class implements simple, dynamic, sorted sequences. Users requiring a data structure for unsorted sequences whose structure and organization is more under the control of the programmer are referred to the N_Tree class. The \f3Binary_Tree<Type>\f1 class is derived from Binary_Tree and is a friend of the Binary_Node< Type > class, also parameterized over the same Type . There is no attempt made to balance or prune the tree. Nodes are added to a particular subtree at the direction of the collating function. For example, a lopsided tree results if a tree is parameterized for integers and the tree uses the default integer comparison operators whose elements are added in increasing order. Likewise, a lopsided tree results after many items have been added and removed. .PP The Binary_Tree< Type > class implements the notion of a current position. This is useful for iterating through the nodes of a tree. The current position is maintained in a data member of type Binary_Tree_state and is set or reset by all member functions affecting elements in the class. Member functions are provided to reset the current position, move to the next and previous elements, find an element, and get the value at the current position. The Iterator< Type > class provides a mechanism to save and restore the state associated with the current position, thus allowing the programmer to use multiple iterators over the same instance of a tree. .SH Base Classes Binary_Tree, .SH Friend Classes None .SH Public Constructors .TP Binary_Tree<Type> (); Allocates a binary tree object with the root pointer set to NULL . .TP \f3Binary_Tree<Type> (const Binary_Tree<Type>& bt\f3);\f1 Duplicates the structure of another binary tree object bt . .SH Member Functions .TP void balance (); Builds a perfectly balanced binary tree from the existing tree structure and deletes the old tree and storage. .TP void clear (); Empties the tree and deallocates all memory for nodes and internal structures. .TP inline long count () const; Returns the number of nodes in the tree structure. .TP inline Binary_Tree_state& current_position (); Returns a reference to the state information associated with the current position. This function should be used with the \f3Iterator<Type>\f1 class to save and restore the current position, thus facilitating multiple iterators over an instance of binary tree. .TP \f3Boolean find (const Type& value\f3);\f1 Searches for value in the tree structure. If found, this function updates the current position and returns TRUE ; otherwise, this function invalidates the current position and returns FALSE . .TP \f3Binary_Node<Type>* \f3get_root () const;\f1 Returns a pointer to the root node of the tree. .TP Boolean next (); Advances the current position to the next element in the tree and returns TRUE . If the current position is invalid, this function sets the current position to the first element and returns TRUE . If the current position is the last element in the tree, this function invalidates the current position and returns FALSE . .TP \f3Binary_Node<Type>* \f3node ();\f1 Returns a pointer to the current node object. .TP \f3Binary_Tree<Type>& \f3operator= (Binary_Tree<Type>& bt\f3);\f1 Overloads the assignment operator to duplicate another binary tree object bt by copying all nodes and value to the binary tree object. This function returns a reference to the updated binary tree object. .TP \f3inline Boolean operator== (const Binary_Tree<Type>& bt\f3) const;\f1 Overloads the equality operator for the \f3Binary_Tree<Type>\f1 class. This function returns TRUE if \f2bt\f1 is equal to the binary tree object; otherwise, this function returns FALSE . .TP \f3inline Boolean operator!= (const Binary_Tree<Type>& bt\f3) const;\f1 Overloads the inequality operator for the \f3Binary_Tree<Type>\f1 class. This function returns TRUE if bt is unequal to the binary tree object; otherwise, this function returns FALSE . .TP Boolean prev (); Moves the current position to the previous element in the tree and returns TRUE . If the current position is invalid, this function sets the current position to the last element and returns TRUE , thus facilitating reverse traversal through the tree. If the current position is the first element in the tree, this function invalidates the current position and returns FALSE . .TP \f3inline Boolean put (const Type& value\f3);\f1 Adds value to the tree structure if not already present. This function returns TRUE if the item is added; otherwise, this function returns FALSE . This function invalidates the current position. .TP inline Boolean remove (); Removes the node at the current position from the tree structure and returns TRUE . This function invalidates the current position of the binary tree object. If the current position is out of range, an \f3\f3Error\f1\f1 exception is raised and this function returns FALSE . .TP \f3inline Boolean remove (const Type& value\f3);\f1 Removes value from the tree structure if present. This function returns TRUE if the specified argument is successfully removed; otherwise, this function returns FALSE . This function invalidates the current position. .TP inline void reset (); Invalidates the current position of the binary tree object. .TP \f3inline void set_compare (\f2Binary_Tree_Compare \f3= NULL);\f1 Sets the comparison function that is to be used in all logical comparison tests. Binary_Tree_Compare is a function of type Boolean (\f2*Function\f1)(\f3const Type&\f1, \f3const Type&\f1). If no argument is provided, the operator== for the type over which the class is parameterized is used. .TP inline long tree_depth (); Returns the zero-relative depth of the tree structure. .TP Type& value (); Returns a reference to the node value at the current position. If the current position is invalid, an \f3\f3Error\f1\f1 exception is raised. .SH Friend Functions .TP \f3friend ostream& operator<< (ostream& \f2os\f3, const Binary_Tree<Type>& bt\f3);\f1 Accepts a binary tree reference and outputs the structure by printing it sideways, where the root is printed at the left margin. To obtain the standard orientation, rotate the output 90 degrees clockwise. This function returns a reference to the output stream. .TP \f3friend ostream& operator<< (ostream& \f2os\f3, const Binary_Tree<Type>* bt\f3);\f1 Accepts a binary tree pointer and outputs the structure by printing it sideways, where the root is printed at the left margin. To obtain the standard orientation, rotate the output 90 degrees clockwise. This function returns a reference to the output stream. .SH COPYRIGHT Copyright (C) 1991 Texas Instruments Incorporated. Permission is granted to any individual or institution to use, copy, modify, and distribute this software, provided that this complete copyright and permission notice is maintained, intact, in all copies and supporting documentation. Texas Instruments Incorporated provides this software "as is" without express or implied warranty. 
